package cn.qyd.leecode;

/**
 * @author 邱运铎
 * @date 2024-03-31 22:56
 */
public class TwoForkTree001_1 {
    public static void main(String[] args) {
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        //定义当前前序遍历的叶子节点数 leafAll 和 节点总数 nodeALl
        //nodeAll通过计算字符串中 , 的数量来计算，所以需要+1，因为总节点是比 ,数量多一个的
        int leafAll = 0, nodeAll = 1;
        for (int i = 0; i < preorder.length(); i++) {
            //一个完整的二叉树叶子节点数量肯定是 非叶子节点数量的 2n+1
            //然后我们遍历到最后肯定是一个叶子节点 #
            //所以在遍历到最后一个叶子节点之前，叶子节点一定不会超过非叶子节点，最多两者相等
            //所以在这个过程中一旦叶子节点数大于非叶子节点，肯定有叶子节点挂在了其他节点，是不合法的二叉树
            if (leafAll > nodeAll - leafAll) System.out.println(false);
            if (preorder.charAt(i) == ',') nodeAll++;
            if (preorder.charAt(i) == '#') leafAll++;
        }

        //最后比较叶子节点 和 非叶子节点是否为 2n+1的关系即可
        System.out.println(leafAll -1 == nodeAll -leafAll);
    }
}
